Jump to content

Concept class

From Wikipedia, the free encyclopedia
(Redirected from Subclass reachability)

In computational learning theory in mathematics, a concept over a domain X is a total Boolean function over X. A concept class is a class of concepts. Concept classes are a subject of computational learning theory.

Concept class terminology frequently appears in model theory associated with probably approximately correct (PAC) learning.[1] In this setting, if one takes a set Y as a set of (classifier output) labels, and X is a set of examples, the map , i.e. from examples to classifier labels (where and where c is a subset of X), c is then said to be a concept. A concept class is then a collection of such concepts.

Given a class of concepts C, a subclass D is reachable if there exists a sample s such that D contains exactly those concepts in C that are extensions to s.[2] Not every subclass is reachable.[2][why?]

Background

[edit]

A sample is a partial function from [clarification needed] to .[2] Identifying a concept with its characteristic function mapping to , it is a special case of a sample.[2]

Two samples are consistent if they agree on the intersection of their domains.[2] A sample extends another sample if the two are consistent and the domain of is contained in the domain of .[2]

Examples

[edit]

Suppose that . Then:

  • the subclass is reachable with the sample ;[2][why?]
  • the subclass for are reachable with a sample that maps the elements of to zero;[2][why?]
  • the subclass , which consists of the singleton sets, is not reachable.[2][why?]

Applications

[edit]

Let be some concept class. For any concept , we call this concept -good for a positive integer if, for all , at least of the concepts in agree with on the classification of .[2] The fingerprint dimension of the entire concept class is the least positive integer such that every reachable subclass contains a concept that is -good for it.[2] This quantity can be used to bound the minimum number of equivalence queries[clarification needed] needed to learn a class of concepts according to the following inequality:.[2]

References

[edit]
  1. ^ Chase, H., & Freitag, J. (2018). Model Theory and Machine Learning. arXiv preprint arXiv:1801.06566.
  2. ^ a b c d e f g h i j k l Angluin, D. (2004). "Queries revisited" (PDF). Theoretical Computer Science. 313 (2): 188–191. doi:10.1016/j.tcs.2003.11.004.